class Solution {
public:
    int pivotIndex(const vector<int>& nums)
    {
        int dp[nums.size()+1];
        dp[0] = 0;
        for (int i = 1; i <= nums.size(); i++)
            dp[i] = dp[i - 1] + nums[i-1];

        for (int j = 0; j < nums.size(); j++)
        {
            if (dp[j] == dp[nums.size()] - dp[j+1])
                return j;
        }
        return -1;
    }
};
